/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package org.apache.tomcat.util.collections;

import java.util.Enumeration;

/*
 * **************************************** Stolen from Crimson
 * ********************
 */
/*
 * From Crimson/Parser - in a perfect world we'll just have a common set of
 * utilities, and all apache project will just use those.
 * 
 */

// can't be replaced using a Java 2 "Collections" API
// since this package must also run on JDK 1.1

/**
 * This class implements a special purpose hashtable. It works like a normal
 * <code>java.util.Hashtable</code> except that:
 * <OL>
 * 
 * <LI> Keys to "get" are strings which are known to be interned, so that "=="
 * is used instead of "String.equals". (Interning could be document-relative
 * instead of global.)
 * 
 * <LI> It's not synchronized, since it's to be used only by one thread at a
 * time.
 * 
 * <LI> The keys () enumerator allocates no memory, with live updates to the
 * data disallowed.
 * 
 * <LI> It's got fewer bells and whistles: fixed threshold and load factor, no
 * JDK 1.2 collection support, only keys can be enumerated, things can't be
 * removed, simpler inheritance; more.
 * 
 * </OL>
 * 
 * <P>
 * The overall result is that it's less expensive to use these in
 * performance-critical locations, in terms both of CPU and memory, than
 * <code>java.util.Hashtable</code> instances. In this package it makes a
 * significant difference when normalizing attributes, which is done for each
 * start-element construct.
 * 
 */
public final class SimpleHashtable implements Enumeration {

	private static org.apache.juli.logging.Log log = org.apache.juli.logging.LogFactory
			.getLog(SimpleHashtable.class);

	// entries ...
	private Entry table[];

	// currently enumerated key
	private Entry current = null;
	private int currentBucket = 0;

	// number of elements in hashtable
	private int count;
	private int threshold;

	private static final float loadFactor = 0.75f;

	/**
	 * Constructs a new, empty hashtable with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the initial capacity of the hashtable.
	 */
	public SimpleHashtable(int initialCapacity) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: "
					+ initialCapacity);
		if (initialCapacity == 0)
			initialCapacity = 1;
		table = new Entry[initialCapacity];
		threshold = (int) (initialCapacity * loadFactor);
	}

	/**
	 * Constructs a new, empty hashtable with a default capacity.
	 */
	public SimpleHashtable() {
		this(11);
	}

	/**
	 */
	public void clear() {
		count = 0;
		currentBucket = 0;
		current = null;
		for (int i = 0; i < table.length; i++)
			table[i] = null;
	}

	/**
	 * Returns the number of keys in this hashtable.
	 * 
	 * @return the number of keys in this hashtable.
	 */
	public int size() {
		return count;
	}

	/**
	 * Returns an enumeration of the keys in this hashtable.
	 * 
	 * @return an enumeration of the keys in this hashtable.
	 * @see Enumeration
	 */
	public Enumeration keys() {
		currentBucket = 0;
		current = null;
		hasMoreElements();
		return this;
	}

	/**
	 * Used to view this as an enumeration; returns true if there are more keys
	 * to be enumerated.
	 */
	public boolean hasMoreElements() {
		if (current != null)
			return true;
		while (currentBucket < table.length) {
			current = table[currentBucket++];
			if (current != null)
				return true;
		}
		return false;
	}

	/**
	 * Used to view this as an enumeration; returns the next key in the
	 * enumeration.
	 */
	public Object nextElement() {
		Object retval;

		if (current == null)
			throw new IllegalStateException();
		retval = current.key;
		current = current.next;
		// Advance to the next position ( we may call next after next,
		// without hasMore )
		hasMoreElements();
		return retval;
	}

	/**
	 * Returns the value to which the specified key is mapped in this hashtable.
	 */
	public Object getInterned(String key) {
		Entry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && (e.key == key))
				return e.value;
		}
		return null;
	}

	/**
	 * Returns the value to which the specified key is mapped in this hashtable
	 * ... the key isn't necessarily interned, though.
	 */
	public Object get(String key) {
		Entry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key))
				return e.value;
		}
		return null;
	}

	/**
	 * Increases the capacity of and internally reorganizes this hashtable, in
	 * order to accommodate and access its entries more efficiently. This method
	 * is called automatically when the number of keys in the hashtable exceeds
	 * this hashtable's capacity and load factor.
	 */
	private void rehash() {
		int oldCapacity = table.length;
		Entry oldMap[] = table;

		int newCapacity = oldCapacity * 2 + 1;
		Entry newMap[] = new Entry[newCapacity];

		threshold = (int) (newCapacity * loadFactor);
		table = newMap;

		/*
		 * System.out.pr intln("rehash old=" + oldCapacity + ", new=" +
		 * newCapacity + ", thresh=" + threshold + ", count=" + count);
		 */

		for (int i = oldCapacity; i-- > 0;) {
			for (Entry old = oldMap[i]; old != null;) {
				Entry e = old;
				old = old.next;

				int index = (e.hash & 0x7FFFFFFF) % newCapacity;
				e.next = newMap[index];
				newMap[index] = e;
			}
		}
	}

	/**
	 * Maps the specified <code>key</code> to the specified <code>value</code>
	 * in this hashtable. Neither the key nor the value can be <code>null</code>.
	 * 
	 * <P>
	 * The value can be retrieved by calling the <code>get</code> method with
	 * a key that is equal to the original key.
	 */
	public Object put(Object key, Object value) {
		// Make sure the value is not null
		if (value == null) {
			throw new NullPointerException();
		}

		// Makes sure the key is not already in the hashtable.
		Entry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index]; e != null; e = e.next) {
			// if ((e.hash == hash) && e.key.equals(key)) {
			if ((e.hash == hash) && (e.key == key)) {
				Object old = e.value;
				e.value = value;
				return old;
			}
		}

		if (count >= threshold) {
			// Rehash the table if the threshold is exceeded
			rehash();

			tab = table;
			index = (hash & 0x7FFFFFFF) % tab.length;
		}

		// Creates the new entry.
		Entry e = new Entry(hash, key, value, tab[index]);
		tab[index] = e;
		count++;
		return null;
	}

	public Object remove(Object key) {
		Entry tab[] = table;
		Entry prev = null;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		if (dL > 0)
			d("Idx " + index + " " + tab[index]);
		for (Entry e = tab[index]; e != null; prev = e, e = e.next) {
			if (dL > 0)
				d("> " + prev + " " + e.next + " " + e + " " + e.key);
			if ((e.hash == hash) && e.key.equals(key)) {
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				if (dL > 0)
					d("Removing from list " + tab[index] + " " + prev + " "
							+ e.value);
				count--;
				Object res = e.value;
				e.value = null;
				return res;
			}
		}
		return null;
	}

	/**
	 * Hashtable collision list.
	 */
	private static class Entry {
		int hash;
		Object key;
		Object value;
		Entry next;

		protected Entry(int hash, Object key, Object value, Entry next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}

	private static final int dL = 0;

	private void d(String s) {
		if (log.isDebugEnabled())
			log.debug("SimpleHashtable: " + s);
	}
}
